package com.caizhigang.dsag.binarysearch;

public class BinarySearch2 {
    public static void main(String[] args) {


        int[] array = {1, 2, 3, 3, 4, 4, 5, 6, 6, 7};
        findFirst(array, 6);
        findLast(array, 6);
        findFirstBigger(array, 6);
        findLastSmaller(array,6);
    }

    /**
     * 查找第一个值等于给定值的元
     */


    public static void findFirst(int[] array, int num) {

        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = (low + high) >> 1;
            if (array[middle] > num) {
                high = middle - 1;
            } else if (array[middle] < num) {
                low = middle + 1;
            } else {
                if (middle == 0 || array[middle - 1] != num) {
                    System.out.println("第一个出现数字" + num + "的下标是:" + middle);
                    return;
                } else {
                    high = middle - 1;
                }
            }
        }
    }

    /**
     * 查找最后一个值等于给定值的元
     */

    public static void findLast(int[] array, int num) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = (low + high) >> 1;
            if (array[middle] > num) {
                high = middle - 1;
            } else if (array[middle] < num) {
                low = middle + 1;
            } else {
                if (middle == array.length - 1 || array[middle + 1] != num) {
                    System.out.println("最后一个出现数字" + num + "的下标是:" + middle);
                    return;
                } else {
                    low = middle + 1;
                }
            }
            System.out.println("第一个比" + num + "大的数字是未找到");
        }
    }

    /**
     * 查找第一个大于等于给定值的元素
     */

    public static void findFirstBigger(int[] array, int num) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = (low + high) >> 1;
            if (array[middle] <= num) {
                low = middle + 1;
            } else {
                if (middle == array.length - 1 || array[middle - 1] <= num) {
                    System.out.println("第一个比" + num + "大的数字是" + array[middle] + "下标是" + middle);
                    return;
                } else {
                    high = middle - 1;
                }
            }
        }
        System.out.println("第一个比" + num + "大的数字是未找到");
    }

    /**
     * 查找最后一个小于等于给定值的元素
     */

    public static void findLastSmaller(int[] array, int num) {
        int low = 0;
        int high = array.length - 1;
        while (low <= high) {
            int middle = (low + high) >> 1;
            if (array[middle] >= num) {
                high = middle - 1;
            } else {
                if (array[middle + 1] >= num) {
                    System.out.println("最后一个小于" + num + "的数字是" + array[middle] + "下标是" + middle);
                    return;
                }else{
                   low=middle+1;
                }
            }
        }
        System.out.println("最后一个比" + num + "小的数字是未找到");
    }

}
